package com.explorati.LeetCode75.sortcolors;

/**
 * 75. Sort Colors 计数法(当元素个数有限时)
 * 
 * Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
 * 
 * @author explorati
 *
 */
public class Solution {

	public static void sortColors(int[] nums) {
		// 由于只有三种取值，所以开辟一个3空间数组 存放0,1,2三个元素的频率
		int[] arr = new int[3];
		for (int i = 0; i < nums.length; i++) {
			// 遍历nums中的元素，将arr相应位置计数+1
			assert nums[i] >= 0 && nums[i] <= 2;
			arr[nums[i]]++;
		}

		// 外部元素k，记录nums遍历到的位置
		int k = 0;
		for (int j = 0; j < arr.length; j++) {
			for (; k < nums.length; k++) {
				// 如果计数为0，跳出循环
				if (arr[j] == 0) {
					break;
				} else {
					// 否则，赋值并将计数--
					nums[k] = j;
					arr[j]--;
				}
			}
		}
	}

	public static void main(String[] args) {
		int[] arr = { 2, 0, 1, 2, 1, 0 };
		sortColors(arr);
		for (int i : arr) {
			System.out.print(i + "  ");
		}
	}
}
